Search results for "Combinatorial optimization problem"
showing 10 items of 11 documents
Intelligent Multi-Start Methods
2018
Heuristic search procedures aimed at finding globally optimal solutions to hard combinatorial optimization problems usually require some type of diversification to overcome local optimality. One way to achieve diversification is to re-start the procedure from a new solution once a region has been explored, which constitutes a multi-start procedure. In this chapter we describe the best known multi-start methods for solving optimization problems. We also describe their connections with other metaheuristic methodologies. We propose classifying these methods in terms of their use of randomization, memory and degree of rebuild. We also present a computational comparison of these methods on solvi…
Scatter search for an uncapacitated p-hub median problem
2015
Scatter search is a population-based method that has been shown to yield high-quality outcomes for combinatorial optimization problems. It uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we present a scatter search implementation for an NP -hard variant of the classic p-hub median problem. Specifically, we tackle the uncapacitated r-allocation p-hub median problem, which consists of minimizing the cost of transporting the traffics between nodes of a network through special facilities that act as transshipment points. This problem has a significant number of applications in practice, such as the design of transportati…
Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows
2019
The split delivery vehicle routing problem with time windows (SDVRPTW) is a notoriously hard combinatorial optimization problem. First, it is hard to find a useful compact mixed-integer programming (MIP) formulation for the SDVRPTW. Standard modeling approaches either suffer from inherent symmetries (mixed-integer programs with a vehicle index) or cannot exactly capture all aspects of feasibility. Because of the possibility to visit customers more than once, the standard mechanisms to propagate load and time along the routes fail. Second, the lack of useful formulations has rendered any direct MIP-based approach impossible. Up to now, the most effective exact algorithms for the SDVRPTW hav…
Branch-and-Bound
2010
We now turn to the discussion of how to solve the linear ordering problem to (proven) optimality. In this chapter we start with the branch-and-bound method which is a general procedure for solving combinatorial optimization problems. In the subsequent chapters this approach will be realized in a special way leading to the so-called branch-and-cut method. There are further possibilities for solving the LOP exactly, e.g. by formulating it as dynamic program or as quadratic assignment problem, but these approaches did not lead to the implementation of practical algorithms and we will not elaborate on them here.
Greedy and K-Greedy algoritmhs for multidimensional data association
2011
[EN] The multidimensional assignment (MDA) problem is a combinatorial optimization problem arising in many applications, for instance multitarget tracking (MTT). The objective of an MDA problem of dimension $d\in\Bbb{N}$ is to match groups of $d$ objects in such a way that each measurement is associated with at most one track and each track is associated with at most one measurement from each list, optimizing a certain objective function. It is well known that the MDA problem is NP-hard for $d\geq3$. In this paper five new polynomial time heuristics to solve the MDA problem arising in MTT are presented. They are all based on the semi-greedy approach introduced in earlier research. Experimen…
Advanced Multi-start Methods
2010
Heuristic search procedures that aspire to find globally optimal solutions to hard combinatorial optimization problems usually require some type of diversification to overcome local optimality. One way to achieve diversification is to re-start the procedure from a new solution once a region has been explored. In this chapter we describe the best known multi-start methods for solving optimization problems. We propose classifying these methods in terms of their use of randomization, memory, and degree of rebuild. We also present a computational comparison of these methods on solving the maximum diversity problem in terms of solution quality and diversification power.
Branch-and-Cut
2010
This chapter focuses on the approach for solving the LOP to optimality which can currently be seen as the most successful one. It is a branch-and-bound algorithm, where the upper bounds are computed using linear programming relax- ations.
Multiobjective GRASP with Path Relinking
2015
In this paper we review and propose different adaptations of the GRASP metaheuristic to solve multiobjective combinatorial optimization problems. In particular, we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with Path Relinking for single-objective optimization. Moreover, we propose different hybridizations of GRASP and Path Relinking for multiobjective optimization. We apply the proposed GRASP with Path Relinking variants to two combinatorial optimization problems, the biobjective orienteering problem and the biobjective path dissimilarity problem. We report …
Greedy Randomized Adaptive Search Procedures
2017
In this chapter, we describe the process of designing heuristic procedures to solve combinatorial optimization problems.
Multi-Start Methods
2006
Heuristic search procedures that aspire to find global optimal solutions to hard combinatorial optimization problems usually require some type of diversification to overcome local optimality. One way to achieve diversification is to re-start the procedure from a new solution once a region has been explored. In this chapter we describe the best known multi-start methods for solving optimization problems. We propose classifying these methods in terms of their use of randomization, memory and degree of rebuild. We also present a computational comparison of these methods on solving the linear ordering problem in terms of solution quality and diversification power.